Menyortir spageti

Menyortir spageti merupakan sebuah algoritma untuk menyortir benda yang diperkenalkan oleh seorang matematikawan asal Kanada, Alexander Dewdney dalam kolomnya di majalah Scientific American. Algoritma ini mengurutkan benda yang membutuhkan ruang untuk menumpuk O(n) yang stabil. Hal ini membutuhkan prosesor paralel.

Algoritma

Untuk sederhananya, mari kita asumsikan kita sedang mengurutkan bilangan asli. Metode, penyortirannya diilustrasikan dengan mengunakan batang spageti mentah.

1. Untuk setiap angka terdapat x di daftar, dapatkan batang dengan panjang x. (Salah satu cara praktis memilih unitnya adalah dengan memilih angka terbesar m dalam daftar dan berkoresponden untuk satu batang spageti yang sempurna. Dalam hal ini satu batang sempurna sama dengan m unit spageti. Untuk mendapat panjang batang x, pecahkan batang (spageti) tersebut menjadi dua, jadi salah satu bagian adalah panjang x dan buang bagian lainnya (yang tidak sama panjang).

2. Setelah mendapat semua batang spageti, ambil batang tersebut dan turunkan dengan perlahan-lahan ke meja, dan biarkan batang spageti tersebut di permukaan meja. Sekarang, untuk setiap batang spageti, turunkan tangan anda dari atas hingga menyentuh batang (Jelas proses ini membingungkan dan menghabiskan waktu). Pindahkan batang tersebut ke dalam daftar output yang sebelumnya kosong. Ulangi langkah tersebut sampai semuanya sudah dipindahkan